#include"bellman-ford.h"
#include<ctime>
#include<cstdlib>

void test1();
void test2();
void test3(int n);

int main(int argc,char *argv[])
{
    test1();
    test2();
    cout<<"验证bellman-ford算法的效率与顶点数的线性关系"<<endl;
    for(int i=1;i<=10;i++)
    {
	test3(10*i);
    }
    return 0;
}

void test1()
{
    cout<<"测试有向有权邻接表图"<<endl;
    DGraph<int> g1(0),g2(0);
    for(int i=1;i<=10;i++)
    {
	g1.insertVertex(i);
	g2.insertVertex(i);
    }
    g1.insertEdge(3,5,2);
    g1.insertEdge(2,3,9);
    g1.insertEdge(7,6,6);
    g1.insertEdge(6,3,8);
    g1.insertEdge(2,5,4);
    g1.insertEdge(5,3,4);
    g1.insertEdge(7,5,9);
    g1.insertEdge(4,5,8);
    g1.insertEdge(1,7,3);
    g1.insertEdge(9,10,1);
    g1.insertEdge(6,8,3);
    g1.insertEdge(4,8,4);
    g1.insertEdge(6,10,4);
    g1.insertEdge(10,2,5);
    g1.insertEdge(5,1,8);
    g1.insertEdge(3,9,2);
    g1.insertEdge(9,1,1);
    g1.insertEdge(1,4,3);
    g1.listEdges();
    g1.BellmanFord(3);
    g1.BellmanFord(5);
    g1.BellmanFord(7);
    g1.BellmanFord(6);

    g2.insertEdge(1,2,4);
    g2.insertEdge(2,6,3);
    g2.insertEdge(6,1,-8);
    g2.BellmanFord(2);
    cout<<"test end"<<endl;
}

void test2()
{
    cout<<"测试有向有权邻接矩阵图"<<endl;
    DGraph<int> g1(1),g2(1);
    for(int i=1;i<=10;i++)
    {
	g1.insertVertex(i);
	g2.insertVertex(i);
    }
    g1.insertEdge(3,5,2);
    g1.insertEdge(2,3,9);
    g1.insertEdge(7,6,6);
    g1.insertEdge(6,3,8);
    g1.insertEdge(2,5,4);
    g1.insertEdge(5,3,4);
    g1.insertEdge(7,5,9);
    g1.insertEdge(4,5,8);
    g1.insertEdge(1,7,3);
    g1.insertEdge(9,10,1);
    g1.insertEdge(6,8,3);
    g1.insertEdge(4,8,4);
    g1.insertEdge(6,10,4);
    g1.insertEdge(10,2,5);
    g1.insertEdge(5,1,8);
    g1.insertEdge(3,9,2);
    g1.insertEdge(9,1,1);
    g1.insertEdge(1,4,3);
    g1.listEdges();
    g1.BellmanFord(3);
    g1.BellmanFord(5);
    g1.BellmanFord(7);
    g1.BellmanFord(6);

    g2.insertEdge(1,2,4);
    g2.insertEdge(2,6,3);
    g2.insertEdge(6,1,-8);
    g2.BellmanFord(2);
    cout<<"test end"<<endl;
}

void test3(int n)
{
    DGraph<int> g1(0);
    for(int i=1;i<=n;i++)
    {
	g1.insertVertex(i);
    }
    for(int j=1;j<=90;j++)
    {
	int v1=(int)(rand()%n+1),v2=(int)(rand()%n+1);
	while(v1==v2||g1.containEdge(v1,v2))
	{
	    v1=(int)(rand()%n+1);
	    v2=(int)(rand()%n+1);
	}
	g1.insertEdge(v1,v2,(int)rand()%10+1);
    }
    clock_t start,end;
    start=clock();
    g1.BellmanFord(3);
    end=clock();
    cout<<n<<" vertexes spent "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
    
    start=clock();
    g1.superBellmanFord(3);
    end=clock();
    cout<<n<<" vertexes spent "<<(double)(end-start)/CLOCKS_PER_SEC<<" s"<<endl;
    return;
}
